// 4. 寻找两个正序数组的中位数

// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
// 请你找出并返回这两个正序数组的 中位数 。

// 算法的时间复杂度应该为 O(log (m+n)) 。

// double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
// {
//     int totalSize = nums1Size + nums2Size;  //计算合并后的数组总长度
//     int* numAll = (int*)malloc(totalSize * sizeof(int));    //动态分配内存
//     //没有分配成功的话，直接释放
//     if(numAll == NULL)
//         free(numAll);

//     int count = 0;

//     int i = 0,j = 0;
//     //合并两个数组长度相同的部分
//     while(i < nums1Size && j < nums2Size)
//     {
//         if(nums1[i] <= nums2[j])
//         {
//             numAll[count++] = nums1[i++];
//         }
//         else
//         {
//             numAll[count++] = nums2[j++];
//         }
//     }

//     //合并长度较长的另一个数组
//     while(i < nums1Size)
//     {
//         numAll[count++] = nums1[i++];
//     }
//     while(j < nums2Size)
//     {
//         numAll[count++] = nums2[j++];
//     }

//     //定义要返回的中位数变量
//     double median;

//     //找中位数
//     if(totalSize % 2 == 1)
//     {
//         median = numAll[totalSize/2];
//     }
//     else
//     {
//         median = (double)(numAll[totalSize/2 - 1] + numAll[totalSize/2])/2;
//     }

//     free(numAll);
//     return median;
// }

// 辅助函数：找到两个有序数组中第k小的元素
double getKth(int *nums1, int nums1Size, int *nums2, int nums2Size, int k)
{
    // 确保nums1是较短数组，减少二分次数
    if (nums1Size > nums2Size)
    {
        return getKth(nums2, nums2Size, nums1, nums1Size, k);
    }
    // 若nums1为空，直接返回nums2的第k-1个元素（下标从0开始）
    if (nums1Size == 0)
    {
        return nums2[k - 1];
    }
    // 若k=1，返回两个数组首元素的较小值
    if (k == 1)
    {
        return fmin(nums1[0], nums2[0]);
    }

    // 确定每次比较的位置（避免数组越界）
    int i = fmin(nums1Size, k / 2);
    int j = k - i;

    // 比较并排除不可能的部分
    if (nums1[i - 1] < nums2[j - 1])
    {
        // 排除nums1的前i个元素，继续找第k-i小的元素
        return getKth(nums1 + i, nums1Size - i, nums2, nums2Size, k - i);
    }
    else
    {
        // 排除nums2的前j个元素，继续找第k-j小的元素
        return getKth(nums1, nums1Size, nums2 + j, nums2Size - j, k - j);
    }
}

// 主函数：计算两个正序数组的中位数
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    int totalSize = nums1Size + nums2Size;
    if (totalSize % 2 == 1)
    {
        // 总长度为奇数，返回第(totalSize+1)/2小的元素
        return getKth(nums1, nums1Size, nums2, nums2Size, (totalSize + 1) / 2);
    }
    else
    {
        // 总长度为偶数，返回第totalSize/2和第totalSize/2+1小的元素的平均值
        double mid1 = getKth(nums1, nums1Size, nums2, nums2Size, totalSize / 2);
        double mid2 = getKth(nums1, nums1Size, nums2, nums2Size, totalSize / 2 + 1);
        return (mid1 + mid2) / 2.0;
    }
}